﻿///////////////////////////////////////////////////////////////////////////////////////////////
// System.Text.Parsing - © 2012 Sebastien Pellizzari
// Released under the MIT License (http://www.opensource.org/licenses/mit-license.php)
///////////////////////////////////////////////////////////////////////////////////////////////

/* NOTE: code inspired from Gardens Point Parser Generator (http://gppg.codeplex.com).
 * How the parse table array is formatted:
 *      - States and rules are encoded linearly in the array. A state ID represents the index of the first int
 *      in the array representing the state, and a rule ID represents the index of the first int in the array
 *      representing the rule.
 *      - int #0: the ID of the initial state.
 *      - int #1: the ID of the final rule.
 *      - Then states are encoded as follows:
 *          - int #0: int 'DefaultAction' representing the default action for entries not in its table.
 *          - int #1: int 'CanShift' determines whether the state has entries in its table for tokens.
 *          - int #2: int 'TableLength' representing the number of entries in its table.
 *          - What follows are the entries of the state table, each in following format:
 *              - int #0: int 'Symbol', one of the symbols expected by the state.
 *              - int #1: int 'Action', the action to perform when the symbol is encountered.
 *      - Then rules are encoded as follows:
 *          - int #0: int 'LHS' representing the symbol at the left-hand side of the rule.
 *          - int #1: int 'RHSLength' representing the length of the right hand side of the rule.
 *          - What follows are the IDs of the 'RHS' array of symbols.
 */

namespace System.Text.Parsing
{
    /*
    /// <summary>Represents the base class for a LALR(1) parser.</summary>
    /// <typeparam name="TRange">The type of symbol range.</typeparam>
    /// <typeparam name="TTokenValue">The type of token value.</typeparam>
    /// <typeparam name="TSymbolValue">The type of symbol value.</typeparam>
    /// <typeparam name="TTokenizer">The type of tokenizer.</typeparam>
    public abstract class LALR1Parser<TRange, TTokenValue, TSymbolValue, TTokenizer> : Parser<TRange, TTokenValue, TTokenizer, TTokenizer>, ITokenizerContext
        where TRange : IDataRange<TRange>
        where TTokenizer : Tokenizer<TRange, TTokenValue>
    {
        private readonly int[] _table;  // Compiled parser table.

        // Parser stuff.
        private int _tokensSinceRecover;                // The number of tokens shifted since recover.
        private bool _gotErrors;                        // Did we get errors?
        private bool _recovering;                       // Are we recovering from an error?
        private TTokenizer _tokenizer;                  // The tokenizer.
        private ParserOptions _options;                 // Parser options.
        private Token<TRange, TTokenValue> _nextToken;  // Next token in the stream.

        // The stack.
        private int _stackIndex;                                            // Index of the top-most element in the stack, or -1 if empty.
        private int[] _stateStack;                                          // The state stack.
        private Symbol<TRange, TTokenValue, TSymbolValue>[] _symbolStack;   // The symbol stack.

        //-----------------------------------------------------------------------
        //     Events
        //-----------------------------------------------------------------------

        /// <summary>Called when an error is detected by the parser.</summary>
        public event ParserErrorHandler<TRange> Error;

        //-----------------------------------------------------------------------
        //     Constructors
        //-----------------------------------------------------------------------

        /// <summary>Initializes an instance of the <see cref="LALR1Parser"/> class.</summary>
        /// <param name="table">The compiled parser table.</param>
        /// <param name="initialStackCapacity">The initial capacity of the parser stack.</param>
        protected LALR1Parser(int[] table, int initialStackCapacity)
        {
            if (table == null) throw new ArgumentNullException("table");
            if (initialStackCapacity <= 0) throw new ArgumentOutOfRangeException("initialStackCapacity");
            _table = table;
            _stackIndex = -1;
            _stateStack = new int[initialStackCapacity];
            _symbolStack = new Symbol<TRange, TTokenValue, TSymbolValue>[initialStackCapacity];
        }

        //-----------------------------------------------------------------------
        //     Methods
        //-----------------------------------------------------------------------

        /// <summary>Initializes the parser.</summary>
        /// <param name="tokenizer">The tokenizer to use.</param>
        /// <param name="options">A set of parsing options.</param>
        public sealed override void Initialize(TTokenizer tokenizer, ParserOptions options)
        {
            if (tokenizer == null) throw new ArgumentNullException("tokenizer");
            _options = options;
            _tokenizer = tokenizer;

            // Initialize the stack.
            _stackIndex = 0;
            _stateStack[0] = _table[INITIALSTATE];

            // Reset the next token.
            _nextToken.TypeId = -1;

            // Reset errors.
            _gotErrors = false;
            _recovering = false;
            _tokensSinceRecover = 0;

            // Initialize user-defined data.
            InternalInitialize();
        }

        /// <summary>Performs a parsing step.</summary>
        /// <returns>The current status of the parsing operation.</returns>
        public sealed override ParserResult Step()
        {
            // Get current state.
            var stateID = _stateStack[_stackIndex];
            var action = GetStateDefaultCation(stateID);

            // If the state has a Token -> Action table...
            if (GetStateCanShift(stateID))
            {
                // If we have read no token yet...
                if (_nextToken.TypeId == -1)
                {
                    // Read a token.
                    do
                    {
                        _tokenizer.Scan(this, out _nextToken);
                    }
                    while (_nextToken.Ignore);

                    // If we reached the end of file...
                    if (_nextToken.TypeId == TokenTypeIds.EOF && (_options & ParserOptions.StopAtEOF) != 0)
                        return ParserResult.StoppedAtEOF;
                }

                // If the current state has a transition for that token, keep it.
                int gotoAction;
                if (TryGetGoToState(stateID, _nextToken.TypeId, out gotoAction))
                    action = gotoAction;

                // If it's an ERROR token and action is SHIFT then set action to ERROR.
                if (_nextToken.TypeId == TokenTypeIds.Error && action > 0)
                    action = 0;
            }

            // If it's a SHIFT action...
            if (action > 0)
            {
                // Shift.
                Shift(action);
            }
            // If it's a REDUCE action...
            else if (action < 0)
            {
                // Reduce.
                Reduce(-action);

                // If it's a HALT...
                if (action == -_table[FINALRULE])
                    return _gotErrors ? ParserResult.CompletedError : ParserResult.CompletedSuccess;
            }
            // Else ERROR.
            else if (action == 0)
            {
                // If option is set to stop at EOF and we're on it, don't recover from the error.
                if (_nextToken.TypeId == TokenTypeIds.EOF && (_options & ParserOptions.StopAtEOF) != 0)
                    return ParserResult.StoppedAtEOF;

                // Try to recover, or fail.
                if (!ErrorRecovery())
                    return ParserResult.CompletedError;
            }

            // Continue.
            return ParserResult.Continue;
        }

        /// <summary>When overriden in a derived class, initializes user-defined parser data.</summary>
        protected abstract void InternalInitialize();

        /// <summary>When overriden in a derived class, executes actions for specified rule.</summary>
        /// <param name="ruleID">The rule ID.</param>
        /// <param name="range">The range of the resulting symbol.</param>
        /// <param name="value">The value of the resulting symbol.</param>
        protected abstract void ExecuteRuleAction(int ruleID, ref TRange range, out TSymbolValue value);

        //-----------------------------------------------------------------------
        //     Non Public
        //-----------------------------------------------------------------------

        // Static fields in the table.
        private const int INITIALSTATE = 0;
        private const int FINALRULE = 1;
        // State fields in the table.
        private const int STATE_DEFAULTACTION = 0;
        private const int STATE_CANSHIFT = 1;
        private const int STATE_TABLELENGTH = 2;
        private const int STATE_TABLE = 3;
        // Rule fields in the table.
        private const int RULE_LHS = 0;
        private const int RULE_RHSLENGTH = 1;
        private const int RULE_RHS = 2;

        // ITokenizerContext.IsExpected method.
        bool ITokenizerContext.IsExpected(int tokenTypeId)
        {
            int gotoStateID;
            return TryGetGoToState(_stateStack[_stackIndex], tokenTypeId, out gotoStateID);
        }

        // Determines whether the transition table of specified state contains transitions for tokens.
        private bool GetStateCanShift(int stateID)
        {
            return _table[stateID + STATE_CANSHIFT] != 0;
        }

        // Returns the default action of specified state.
        private int GetStateDefaultCation(int stateID)
        {
            return _table[stateID + STATE_DEFAULTACTION];
        }

        // Tries to find the GOTO state or the action in the transition table of specified state.
        private bool TryGetGoToState(int stateID, int symbolOrTokenID, out int actionOrStateID)
        {
            var len = _table[stateID + STATE_TABLELENGTH];
            for (int i = 0; i < len; i++)
                if (_table[stateID + STATE_TABLE + 2 * i] == symbolOrTokenID)
                {
                    actionOrStateID = _table[stateID + STATE_TABLE + 2 * i + 1];
                    return true;
                }
            actionOrStateID = 0;
            return false;
        }

        // Prepares a Push operation on the stack.
        private void StackPush()
        {
            _stackIndex++;
            if (_stackIndex == _stateStack.Length)
            {
                Array.Resize(ref _stateStack, 2 * _stateStack.Length);
                Array.Resize(ref _symbolStack, 2 * _symbolStack.Length);
            }
        }

        // Shifts a token onto the stack.
        private void Shift(int stateID)
        {
            // Push token onto the stack.
            StackPush();
            _stateStack[_stackIndex] = stateID;
            _symbolStack[_stackIndex].Range = _nextToken.Range;
            _symbolStack[_stackIndex].TypeId = _nextToken.TypeId;
            _symbolStack[_stackIndex].TokenValue = _nextToken.Value;

            // If we're recovering...
            if (_recovering)
            {
                if (_nextToken.TypeId != TokenTypeIds.Error)
                    _tokensSinceRecover++;
                if (_tokensSinceRecover > 0)
                    _recovering = false;
            }

            // If EOF not reached, reset the current token index.
            if (_nextToken.TypeId != TokenTypeIds.EOF)
                _nextToken.TypeId = -1;
        }

        // Reduces symbols on top of the stack using the specified rule.
        private void Reduce(int ruleID)
        {
            var ruleLhs = _table[ruleID + RULE_LHS];
            var ruleRhsLength = _table[ruleID + RULE_RHSLENGTH];

            // Compute the symbol range.
            TRange range;
            switch (ruleRhsLength)
            {
                case 0:
                    // Empty range.
                    _nextToken.Range.GetEndRange(out range);
                    break;
                case 1:
                    // @@ = @1;
                    range = _symbolStack[_stackIndex].Range;
                    break;
                default:
                    // @@ = @1.Merge(@N);
                    _symbolStack[_stackIndex - ruleRhsLength + 1].Range.MergeWith(ref _symbolStack[_stackIndex].Range, out range);
                    break;
            }

            // Execute the action bound to that rule.
            TSymbolValue symbolValue;
            ExecuteRuleAction(ruleID, ref range, out symbolValue);

            // Pop a number of items equal to the number of symbols on the rhs of the rule.
            _stackIndex -= ruleRhsLength;
            var topStateID = _stateStack[_stackIndex];

            // Allocate one more index onto the stack.
            StackPush();
            _symbolStack[_stackIndex].Range = range;
            _symbolStack[_stackIndex].TypeId = ruleLhs;
            _symbolStack[_stackIndex].SymbolValue = symbolValue;

            // Make a transition to another state if necessary.
            int gotoStateID;
            if (TryGetGoToState(topStateID, ruleLhs, out gotoStateID))
                _stateStack[_stackIndex] = gotoStateID;
        }

        // Reports an error if necessary, and tries to find a state to go on.
        private bool ErrorRecovery()
        {
            // If the current state is an error...
            if (_symbolStack[_stackIndex].TypeId == TokenTypeIds.Error)
            {
                if (_nextToken.TypeId != TokenTypeIds.EOF)
                {
                    // Concatenate it.
                    _symbolStack[_stackIndex].Range.MergeWith(ref _nextToken.Range, out _symbolStack[_stackIndex].Range);
                }
            }
            else
            {
                // Turn the current state into an error.
                _symbolStack[_stackIndex].Range = _nextToken.Range;
                _symbolStack[_stackIndex].TypeId = _nextToken.TypeId == TokenTypeIds.EOF ? TokenTypeIds.EOF : TokenTypeIds.Error;
            }

            // Look backwards for a state in the stack that is able to handle errors.
            var errorStateID = -1;
            var foundErrorTransition = false;
            var handlerStateIndexInStack = -1;
            for (int i = _stackIndex; i >= 0; i--)
                if (GetStateCanShift(_stateStack[i]) && TryGetGoToState(_stateStack[i], TokenTypeIds.Error, out errorStateID))
                {
                    handlerStateIndexInStack = i;
                    foundErrorTransition = true;
                    break;
                }

            // If we found one...
            if (foundErrorTransition)
            {
                // Pop all the states inbetween.
                _stackIndex = handlerStateIndexInStack;

                // Push the ERROR token on the stack.
                StackPush();
                _stateStack[_stackIndex] = errorStateID;
                _symbolStack[_stackIndex].Range = _nextToken.Range;
                _symbolStack[_stackIndex].TokenValue = default(TTokenValue);
                _symbolStack[_stackIndex].SymbolValue = default(TSymbolValue);

                // If EOF not reached, reset the current ERROR token.
                if (_nextToken.TypeId != TokenTypeIds.EOF)
                    _nextToken.TypeId = -1;

                // Discard upcoming tokens until the current state is able to go on.
                bool discard;
                if (GetStateCanShift(errorStateID))
                {
                    // Discard tokens until we find one that works...
                    for (; ; )
                    {
                        // Fetch a token if necessary.
                        if (_nextToken.TypeId == -1)
                            do
                            {
                                _tokenizer.Scan(this, out _nextToken);
                                if (_nextToken.TypeId == TokenTypeIds.Error)
                                    _symbolStack[_stackIndex].Range.MergeWith(ref _nextToken.Range, out _symbolStack[_stackIndex].Range);
                            }
                            while (_nextToken.Ignore);

                        // If EOF reached, error.
                        if (_nextToken.TypeId == TokenTypeIds.EOF)
                        {
                            discard = false;
                            break;
                        }
                        else
                        {
                            // If current state can go on with this token, and it doesn't lead to an ERROR action, then go with it.
                            int action;
                            if (TryGetGoToState(errorStateID, _nextToken.TypeId, out action) && action != 0)
                            {
                                discard = true;
                                break;
                            }
                            else
                            {
                                // Empty the token so we can read another one.
                                _nextToken.TypeId = -1;
                            }
                        }
                    }
                }
                else if (_recovering && _tokensSinceRecover == 0)
                {
                    // _recovering is not set until after the first error token has been shifted. Thus if we get back here
                    // with recovering set and no tokens read we are looping on the same error recovery action. This happens
                    // if the table of current state is empty because the state has an LR(0) reduction, but not all lookahead
                    // tokens are valid. This only occurs for error productions that *end* on "error".
                    // This action discards tokens one at a time until the looping stops. Another attack would be to always
                    _nextToken.TypeId = -1;
                    discard = true;
                }
                else discard = true;

                // If we're not recovering...
                if (!_recovering)
                {
                    if (Error != null) Error(_symbolStack[_stackIndex].Range);
                }

                _recovering = true;
                _tokensSinceRecover = 0;

                // Tell if we were able to recover.
                return discard;
            }
            else
            {
                // We finished recovering.
                _recovering = false;

                // Report that error.
                if (Error != null) Error(_symbolStack[_stackIndex].Range);

                // We were unable to recover from that error.
                return false;
            }
        }
    }*/
}
